package pers.qianyu.month_202101.date_20210119;

import org.junit.*;

import java.util.*;

/**
 * 131. 分割回文串
 * https://leetcode-cn.com/problems/palindrome-partitioning/
 *
 * @author mizzle rain
 * @date 2021-01-19 18:28
 */
public class PalindromePartitioning {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        ArrayList<String> path = new ArrayList<>();
        backTracking(path, s, 0);
        return res;
    }

    private void backTracking(ArrayList<String> path, String s, int cur) {
        int len = s.length();
        if (len == cur) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = cur; i < len; i++) {
            if (isValid(s, cur, i)) {
                path.add(s.substring(cur, i + 1));
                backTracking(path, s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isValid(String s, int left, int right) {
        while (left <= right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void test1() {
        List<List<String>> result = new PalindromePartitioning().partition("aab");
        System.out.println("result = " + result);
    }
}
